// g++ -O3 src/Common.cpp examples/hash_10_search.cpp -Isrc/ -o bin/hash10

#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include "Common.h"

using namespace std;

static uint HashStringHack(const char *str, uint scatter[10]){
	uint result = 0;
	while(*str){
		result = ((result<<1) ^ (result>>(8*sizeof(uint)-1))) ^ scatter[*str - '0'];
		++str;
	}
	return result;	
}

static uint BinaryHashStringHack(const char *str, uint *scatter){
	uint result = 0;
	uint s[2] = { scatter[0], scatter[1] };
	while(*str){
		uint8_t v = *str;
		for(int i = 0; i < 8; ++i){
			if(result & 1){
				result = ((result<<1) ^ (result>>(8*sizeof(uint)-1)));
			}
			else{
				result = ((result<<13) ^ (result>>(8*sizeof(uint)-13)));
			}
			if( (result&1) == (v&1) ){
				uint tmp = s[0];
				s[0] = ((s[0]<<1) ^ (s[1]>>(8*sizeof(uint)-1)));
				s[1] = ((s[1]<<1) ^ (tmp>>(8*sizeof(uint)-1)));
			}
			else{
				uint tmp = s[0];
				s[0] = ((s[0]<<7) ^ (s[1]>>(8*sizeof(uint)-7)));
				s[1] = ((s[1]<<7) ^ (tmp>>(8*sizeof(uint)-7)));				
			}
			result ^= s[v&1];
			v >>= 1;
		}
		++str;
	}
	return result;	
}

static void generate_scatter(uint scatter[10]){
	for(int i = 0; i < 10; ++i){ 
		uint r1 = rand();
		uint r2 = rand();
		uint r = (r1 << 16) | (r2 >> 16);
		scatter[i] = r;
	}
}

static void to_string(char *buffer, uint num, int base){
	if(base == 10){
		uint factor = 100000;
		while(num > factor){
			factor *= 10;
		}
		int i = 0;
		while(factor){
			uint part = num / factor;
			if(part || i > 0){
				buffer[i++] = '0' + part;
			}
			num -= factor*part;
			factor /= 10;
		}
		if(i == 0){
			buffer[i++] = '0';
		}
		buffer[i] = 0;
	}
	else{
		int i = 0;
		for(int bit = 0; bit < 8*sizeof(num); ++bit){
			if(num & 0x80000000){
				buffer[i++] = '1';
			}
			else if(i > 0){
				buffer[i++] = '0';
			}
			num <<= 1;
		}
		if(i == 0){
			buffer[i++] = '0';
		}
		buffer[i] = 0;
		//puts(buffer);
	}
}

class AllValues{
public:
	AllValues(){
		Assert(sizeof(char) == 1);
		arraySize = ArraySize();
		cellSize = 8*sizeof(*all);
		all = new uint[arraySize];
		Clear();
	}
	
	~AllValues(){
		delete[] all;
	}
	
	void Clear(){ 
		//memset(all, 0, sizeof(*all)*arraySize); 
		 for(int i = 0; i < arraySize;){
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
			 all[i++] = 0;
		 }
	}
	
	bool Get(uint index){
		return all[index/cellSize] & (1UL << (index % cellSize));
	}
	
	void Set(uint index){
		uint *cell = all + index/cellSize;
		cell[0] |= (1UL << (index % cellSize));
		/*
		 Assert(Get(index));
		if(!Get(index)){
			printf("%lu is not set\n", index);
			printf("cell[%i], bit-%i\n", int(index/cellSize), int(bit));
		}
		*/
	}
	
private:
	uint ArraySize(){
		Assert(sizeof(uint) == 4);
		return 134217728; // (2^32)/32
	}
	
	uint arraySize;
	uint cellSize;
	uint *all; // a HUGE array to record each hash value
};

static uint count_ones(uint x){
	uint result = 0;
	while(x){
		if(x & 1){ result += 1; }
		x >>= 1;
	}
	return result;
}

class Scatter{
public:
	Scatter(const char *mode, uint initial){
		if(*mode == 'n'){
			numerical = true;
			numEntries = 10;
			minChar = '0';
		}
		else if(*mode == 'b'){ // binary
			numerical = true;
			numEntries = 2;
		}
		else{
			numerical = false;
			numEntries = 26;
			minChar = 'a';			
		}
		scatter = new uint[numEntries];
		cellSize = 8*sizeof(*scatter);
		for(int i = start(); i < end(); ++i){
			if(initial){
				Set(i);
			}
			else{
				Clear(i);
			}
		}
	}
	
	~Scatter(){
		delete scatter;
	}
	
	void SetScatter(uint values[], uint num){
		if(num != numEntries){ puts("wrong number of entries"); return; }
		for(int i = 0; i < numEntries; ++i){
			scatter[i] = values[i];
		}
	}

	uint Randomize(){
		for(int i = 0; i < numEntries; ++i){ 
			uint r1 = rand();
			uint r2 = rand();
			uint r = (r1 << 16) | (r2 >> 16);
			scatter[i] = r;
		}
		return Overlap();
	}
	
	uint CountBits() const{
		uint result = 0;
		for(int i = 0; i < numEntries; ++i){ 
			result += count_ones(scatter[i]);
		}
		return result;
	}
	
	uint Overlap() const{
		uint result = 0;
		for(int i = 0; i < numEntries; ++i){ 
			for(int j = i+1; j < numEntries; ++j){ 
				uint target = scatter[j];
				for(uint rot = 0; rot < 8*sizeof(target); ++rot){
					result += count_ones(scatter[i] & target);
					target = ((target<<1) ^ (target>>(8*sizeof(uint)-1)));
				}				
			}
		}
		return result;
	}
	
	uint Hash(const char *str){
		uint result = 0;
		while(*str){
			result = ((result<<1) ^ (result>>(8*sizeof(uint)-1))) ^ scatter[*str - minChar];
			++str;
		}
		return result;	
	}

	void Clear(int index){ 
		uint *cell = scatter + index/cellSize;
		cell[0] &= ~(1UL << (index % cellSize));
	}
	
	bool Get(uint index){
		return scatter[index/cellSize] & (1UL << (index % cellSize));
	}
	
	void Set(uint index){
		uint *cell = scatter + index/cellSize;
		cell[0] |= (1UL << (index % cellSize));
	}
	
	int start() const{ return 0; }
	int end() const{ return cellSize*numEntries; }
	
	uint FirstBinaryHashCollision(){
		map< uint, uint > seen;
		for(uint i = 0; 1==1; ++i){
			char buffer[200];
			to_string(buffer, i, 10);
			Message msg = BinaryHashStringHack(buffer, scatter);
			if(seen.find(msg) != seen.end()){
				return i;
			}
			seen[msg] = i;
			//printf("\t%i: %s -> %u\n", i, buffer, msg);
		}							
	}

	uint FirstCollision(uint estimate = 0){
		if(numEntries == 2){ return FirstBinaryHashCollision(); }
		if(estimate < 500000){
			map< uint, uint > seen;
			for(uint i = 0; 1==1; ++i){
				char buffer[200];
				to_string(buffer, i, numEntries);
				Message msg = HashStringHack(buffer, scatter);
				if(seen.find(msg) != seen.end()){
					return i;
				}
				seen[msg] = i;
				//printf("%i. %s -> %u\n", i, buffer, msg);
			}					
		}
		else{
			static AllValues seen;
			seen.Clear();
			for(uint i = 0; 1==1; ++i){
				char buffer[200];
				to_string(buffer, i, numEntries);
				Message msg = HashStringHack(buffer, scatter);
				if(seen.Get(msg)){
					return i;
				}
				seen.Set(msg);
			}		
		}
	}
	
	bool Complete() const{
		for(int i = 0; i < numEntries; ++i){
			if(scatter[0] != scatter[i]){ return false; }
		}		
		return true;
	}
	
	void Print(){
		for(int i = 0; i < numEntries; ++i){
			printf("0x%X, ", scatter[i]);
		}
		puts("");		
	}
	
private:
	bool numerical;
	uint numEntries;
	char minChar;
	uint cellSize;
	uint *scatter; 
};

static void add(Scatter &scatter){
	uint best = 0;
	int bestIndex = -1;
	for(int i = scatter.start(); i < scatter.end(); ++i){
		if(!scatter.Get(i)){
			scatter.Set(i);
			uint collision = scatter.FirstCollision(best);
			scatter.Clear(i);
			if(collision > best){
				best = collision;
				bestIndex = i;
				//printf("\t%u\n", best);
			}
		}
	}
	if(bestIndex >= 0){
		scatter.Set(bestIndex);
		printf("%u, %u, add -> ", scatter.CountBits(), best);
		scatter.Print();	
	}
}

static void remove(Scatter &scatter){
	uint best = 0;
	int bestIndex = -1;
	for(int i = scatter.start(); i < scatter.end(); ++i){
		if(scatter.Get(i)){
			scatter.Clear(i);
			uint collision = scatter.FirstCollision(best);
			scatter.Set(i);
			if(collision > best){
				best = collision;
				bestIndex = i;
				//printf("\t%u\n", best);
			}
		}
	}
	if(bestIndex >= 0){
		scatter.Clear(bestIndex);
		printf("%u, %u, remove -> ", scatter.CountBits(), best);
		scatter.Print();
	}
}

static void build_scatter(){
	uint initial = 0;
	//Scatter scatter("numerical", initial);
	Scatter scatter("binary", initial);
	//uint start[] = { 0x90A80221, 0x40088446, 0x10D1A1D, 0x593A927E, 0x98908483, 0x3070E32E, 0x9DEC5AED, 0x94BA828B, 0x1A06CC30, 0xD39E5343 };
	//scatter.SetScatter(start, sizeof(start)/sizeof(*start));
	bool backtrack = true;
	while(1){
		if(initial){
			if(backtrack){ 
				add(scatter);
				remove(scatter);
			}
			remove(scatter);
		}
		else{
			if(backtrack){ 
				remove(scatter);			
				add(scatter);
				remove(scatter);			
				add(scatter);
			}
			add(scatter);
		}
		if(scatter.Complete()){
			break;
		}
	}
}

static void overlap_correlation(){
	Scatter scatter("numerical", 0);
	for(uint i = 0; i < 1000; ++i){
		uint overlap = scatter.Randomize();
		uint collision = scatter.FirstCollision();
		printf("%u, %u\n", overlap, collision);
	}
}

static uint first_collision(uint scatter[10]){
	static AllValues seen;
	seen.Clear();
	for(uint i = 0; 1==1; ++i){
		char buffer[200];
		//sprintf(buffer, "%u", i);
		to_string(buffer, i, 10);
		Message msg = HashStringHack(buffer, scatter);
		if(seen.Get(msg)){
			return i;
		}
		seen.Set(msg);
	}
}

static void numerical_scatter_search(){
	uint scatter[10];
	uint best = 0;
	//uint seedStart = time(0);
	srand(time(0));
	while(1==1){
		//uint seed = seedStart + clock();
		generate_scatter(scatter);
		uint collision = first_collision(scatter);
		if(collision > best){
			best = collision;
			printf("%u before collision\n", collision);
			for(int i = 0; i < 10; ++i){
				printf("0x%X, ", scatter[i]);
			}
			puts("");			
		}
	}
}

static void find_index_collision(){
	map< Message, uint > seen;
	for(uint i = 0; i < 200000000; ++i){
		char buffer[200];
		sprintf(buffer, "%u", i);
		Message msg = HashString(buffer);
		if(seen.find(msg) != seen.end()){
			printf("%u collides with %u\n", i, seen[msg]);
			break;
		}
		seen[msg] = i;
	}	
}

#define ALL_ENGLISH false

#if ALL_ENGLISH
#include "english_all.cpp"

uint do_word(map< Message, string > &seen, const char *word){
	Message msg = HashString(word);
	if(seen.find(msg) != seen.end()){
		if(string(word) != seen[msg]){
			printf("%s != %s\n", word, seen[msg].c_str());
			return 1;
		}
	}
	seen[msg] = string(word);
	return 0;
}

void optimise_english_hash(){
	uint count = 0;
	map< Message, string > seen;
	for(int i = 0; i < sizeof(allWords)/sizeof(*allWords); ++i){
		count += do_word(seen, allWords[i]);
	}
	char suffix[] = "0";
	for(int i = 0; i < sizeof(allWords)/sizeof(*allWords); ++i){
		for(int j = 0; j < 3; ++j){
			string s(allWords[i]);
			suffix[0] = '0' + j;
			s += suffix;
			count += do_word(seen, s.c_str());
		}
	}
	for(int i = 0; i < sizeof(allWords)/sizeof(*allWords); ++i){
		string s(allWords[i]);
		s[0] = s[0] + ('A' - 'a');
		count += do_word(seen, s.c_str());
	}
	printf("%i\n", count);
}

#endif

int main (int argc, char * const argv[]) {
#if ALL_ENGLISH
	optimise_english_hash();
#endif

	//overlap_correlation();
	build_scatter();
    //find_index_collision();
	//numerical_scatter_search();
    return 0;
}


